/*
 * @Author: szx
 * @Date: 2022-05-19 13:57:23
 * @LastEditTime: 2022-05-19 14:19:48
 * @Description:
 * @FilePath: \leetcode\面试题\04\09\09.js
 */

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var BSTSequences = function (root) {
    if (!root) return [[]];
    const queue = [root],
        result = [],
        res = [];
    function dfs() {
        for (let i = 0; i < queue.length; i++) {
            const node = queue[i];
            res.push(node.val);
            queue.splice(i, 1);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
            if (queue.length) dfs();
            else result.push(Array.from(res));
            node.right && queue.pop();
            node.left && queue.pop();
            queue.splice(i, 0, node);
            res.pop();
        }
    }
    dfs();
    return result;
};

var BSTSequences = function (root) {
    const res = [];
    if (root == null) return [[]];
    const queue = [];

    let dfs = (root, queue, temp) => {
        if (root == null) return;
        if (root.left) queue.push(root.left);
        if (root.right) queue.push(root.right);
        if (!queue.length) {
            res.push(Array.from(temp));
            return;
        }
        let { length } = queue;
        while (length--) {
            let cur = queue.shift();
            dfs(cur, queue.slice(), [...temp, cur.val]);
            queue.push(cur);
        }
    };

    dfs(root, res, queue, [root.val]);
    return res;
};

// javascript
var BSTSequences = function (root) {
    if (root === null) return [[]];
    const res = [];
    var findPath = function (cur, queue, path) {
        // 传入 cur 形参
        if (cur.left) queue.push(cur.left);
        if (cur.right) queue.push(cur.right);
        if (queue.length === 0) {
            // 终止条件
            res.push(path); // 存放结果
            return;
        }
        for (let i = 0; i < queue.length; i++) {
            let newQueue = queue.slice(0, i).concat(queue.slice(i + 1, queue.length));
            // 构造新数组，newQueue 其实是将 queue[i] 删除后的数组
            findPath(queue[i], newQueue, [...path.queue[i].val]);
        }
    };
    findPath(root, [], [root.val]);
    return res;
};
